package kibahed.university.effizientealgorithmen.algortihms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Set;

import kibahed.university.effizientealgorithmen.fileinteractions.TspLibComparer;
import kibahed.university.effizientealgorithmen.interfaces.AAlgorithm;
import kibahed.university.effizientealgorithmen.interfaces.IEdge;
import kibahed.university.effizientealgorithmen.interfaces.IGraph;
import kibahed.university.effizientealgorithmen.interfaces.IVertex;
import kibahed.university.effizientealgorithmen.standardclasses.CostLine;
import kibahed.university.effizientealgorithmen.standardclasses.EdgeWithCosts;

public class CircleSearch_MaxDistance extends AAlgorithm {

	PriorityQueue<EdgeWithCosts> queue = new PriorityQueue<EdgeWithCosts>();
	Set<IEdge> minimalSpanningTree = new HashSet<IEdge>();

	int[] parts = null;
	int[] sz = null;

	@SuppressWarnings("unchecked")
	public CircleSearch_MaxDistance(IGraph graph) {
		setGraph(graph);
		queue.addAll((Collection<? extends EdgeWithCosts>) graph.getEdges());
		parts = new int[graph.getVertexes().length];
		initParts();
		sz = new int[graph.getVertexes().length];
	}

	private void initParts() {
		for (int i = 0; i < parts.length; i++) {
			parts[i] = i;
		}
	}

	private void updateParts(int start, int end) {
		int newEnd = parts[end];
		for (int i = 0; i < parts.length; i++) {
			if (parts[i] == newEnd) {
				parts[i] = parts[start];
			}
		}
	}

	@Override
	public void calculate() {
		addConsoleText("STARTING CIRCLE SEARCH - MAX DISTANCE");
		addConsoleText("Graph : "+graph.getTspName());
		addConsoleText("Best known solution for "+graph.getTspName()+" : "+TspLibComparer.getResult(graph.getTspName()));
		double[][] costs = graph.getCostMatrix();
		PriorityQueue<CostLine> queue = new PriorityQueue<CostLine>();
		for(int i=0;i<costs.length;i++){
			CostLine line= new CostLine(costs[i],i);
			queue.add(line);
		}
		LinkedList<IVertex> availableNodes = new LinkedList<IVertex>();
		for(IVertex vertex:graph.getVertexes()){
			availableNodes.add(vertex);
		}
		//first two Nodes
		ArrayList<IVertex> tour = new ArrayList<IVertex>();
		CostLine line0 = queue.remove();
		IVertex vertex0 = graph.getVertexes()[line0.getVertex()];
		tour.add(vertex0);
		availableNodes.remove(vertex0);
//		line0 = queue.remove();
//		vertex0 = graph.getVertexes()[line0.getVertex()];
//		tour.add(vertex0);
//		availableNodes.remove(vertex0);
		
		
		do{
//			CostLine line = queue.remove();
//			IVertex vertex = graph.getVertexes()[line.getVertex()];
			double minDist = Double.MIN_VALUE;
			IVertex vertex=availableNodes.getFirst();
			for(IVertex vertexOfTour:tour){
				for(int i=0;i<costs[0].length;i++){
					double current;
					if(availableNodes.contains(graph.getVertexes()[i])){
						if((current=costs[vertexOfTour.getID()][i])<minDist&&(current=costs[vertexOfTour.getID()][i])>0)
						{
							minDist=current;
							vertex=graph.getVertexes()[i];
						}
					}
				}
			}
			availableNodes.remove(vertex);
			int node0 = vertex.getID();
			int storedPosition=0;
			double min=Double.MAX_VALUE;
			for(int i=0;i<tour.size();i++){
				int position=0;
				int node1=tour.get(i).getID();
				int node2=0;
				if(i+1==tour.size()){
					node2=tour.get(0).getID();
					
				}else{
					node2=tour.get(i+1).getID();
					position=i+1;
				}
				
				double sum=costs[node0][node1]+costs[node0][node2] - costs[node1][node2];
				if(sum<min){
					min=sum;
					storedPosition=position;
				}
			}
			tour.add(storedPosition, vertex);
			
			
		}while(!availableNodes.isEmpty());
		
		ArrayList<IEdge> edges = new ArrayList<IEdge>();
		
		for(int i=0;i<tour.size();i++){
			IVertex vertex1=tour.get(i);
			IVertex vertex2;
			if(i+1==tour.size()){
				vertex2=tour.get(0);
			}else{
				vertex2 = tour.get(i+1);
			}
			edges.add(graph.getEdgeBetweenVertices(vertex1.getID(), vertex2.getID()));
		}
		this.setResult(edges.toArray(new IEdge[edges.size()]));
		
		this.addConsoleText("length of tour = "+getIntegerTourLength());
		graph.addMessages(this.getConsoleText());
	}
		
}
